package org.example.basic;

import lombok.Data;
import org.example.util.DisJointSet;

import java.io.*;
import java.util.*;

@Data
public class CoreCommunity {

    private int start = 0x3f3f3f3f;

    private int end = 0;

    // 输入的边
    private List<Edge> edgeList;

    // 每个顶点的core
    private int[] core;

    //邻接表
    private List<AdjacencyEdge> adjacencyEdgeList;

    public void kCoreCommunitySearch(int k, String inputFileName, String outputFileName, String regex) {
        // 读入数据
        readFile(inputFileName, regex);

        if (end - start <= 0) {
            System.out.println("顶点数错误!!!");
            System.out.println("start=" + start + ", end=" + end);
            return;
        }

        coreDecomposition();
        // 将结果写入文件
        //writeFile(core, outputFileName);

        DisJointSet disJointSet = new DisJointSet(end);

        boolean[] flag = new boolean[end + 1];
        for (Edge edge : edgeList) {
            int u = edge.getU();
            int v = edge.getV();
            if (core[u] >= k && core[v] >= k) {
                disJointSet.join(u, v);
                flag[u] = true;
                flag[v] = true;
            }
        }
        int[] pre = new int[end + 1];

        // 更新每个节点的祖先节点
        for (int i = start; i <= end; ++i) {
            pre[i] = disJointSet.find(i);
//            System.out.printf("pre[%d]=%d\n", i, pre[i]);
        }

        int maxCommunitySize = 0;
        int communityCount = 0;
        int nodeCount = 0;
        for (int i = start; i <= end; ++i) {
            if (flag[i] && pre[i] == i) {
                ++communityCount;
                System.out.printf("第" + communityCount + "个社区的成员为：");
                int num = 0;
                for (int j = start; j <= end; ++j) {
                    if (pre[j] == i) {
                        ++num;
                        System.out.printf("%d ", j);
                    }
                }
                nodeCount += num;
                maxCommunitySize = Math.max(maxCommunitySize, num);
                System.out.println();
                System.out.println("第" + communityCount + "个社区总共有" + num + "个成员");
            }
        }

        System.out.println("共找到" + communityCount + "个" + k + "-core社区");
        if (communityCount != 0) {
            int avgCommunitySize = nodeCount / communityCount;
            System.out.println("其中最大的社区的大小为" + maxCommunitySize + "，平均社区大小为" + avgCommunitySize);
            dataStatistics(maxCommunitySize, communityCount, avgCommunitySize, k, outputFileName);
        } else {
            dataStatistics(0, 0, 0, k, outputFileName);
        }
    }

    public void dataStatistics(int maxCommunitySize, int communityCount, int avgCommunitySize, int k, String outputFileName) {
        try {
            String line = k + " " + communityCount + " " + maxCommunitySize + " " + avgCommunitySize + "\n";
            FileWriter fileWriter = new FileWriter(outputFileName, true);
            fileWriter.write(line);
            fileWriter.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public void readFile(String inputFileName, String regex) {
        try {
            BufferedReader reader = new BufferedReader(new FileReader(inputFileName));
            String line;

            // 标识边(x,y)是否已经存储
            Map<String, Boolean> edgeExist = new HashMap<>();
            edgeList = new ArrayList<>();
            int u, v, x, y;
            String str;
            while ((line = reader.readLine()) != null) {
                // 不是数字则数据不对
                if (line.charAt(0) > '9' || line.charAt(0) < '0') {
                    continue;
                }
                String[] words = line.split(regex);
                if (words.length != 2) {
                    continue;
                }
                u = Integer.parseInt(words[0].trim());
                v = Integer.parseInt(words[1].trim());
                // 去除自环
                if (u == v) {
                    continue;
                }
                start = Math.min(start, Math.min(u, v));
                end = Math.max(Math.max(u, v), end);

                x = Math.min(u, v);
                y = u ^ v ^ x;
                str = x + "-" + y;
                // 去除重边
                if (edgeExist.containsKey(str)) {
                    continue;
                }
                edgeExist.put(str, true);
                edgeList.add(new Edge(x, y));
            }
            reader.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    /**
     * // 无向图添加边
     *
     * @param first
     * @param degree
     * @return
     */
    public void addEdge(int[] first, int[] degree) {
        for (int i = start; i <= end; ++i) {
            first[i] = -1;
        }
        adjacencyEdgeList = new ArrayList<>();
        int size = 0;
        // 添加边
        // 使用邻接表存储
        for (Edge edge : edgeList) {
            int u = edge.getU();
            int v = edge.getV();
            adjacencyEdgeList.add(new AdjacencyEdge(v, first[u]));
            first[u] = size++;
            ++degree[u];
            adjacencyEdgeList.add(new AdjacencyEdge(u, first[v]));
            first[v] = size++;
            ++degree[v];
        }
    }

    public void updateNodeDegree(int u, boolean[] deleteFlag, int[] degree, int[] first) {
        // 更新剩余顶点的度
        for (int i = first[u]; i != -1; i = adjacencyEdgeList.get(i).getNext()) {
            int v = adjacencyEdgeList.get(i).getV();
            if (!deleteFlag[v]) {
                --degree[v];
            }
        }
    }
    public void writeFile(int[] core, String outputFileName) {
        try {
            BufferedWriter writer = new BufferedWriter(new FileWriter(outputFileName));
            int maxCore = 0;
            for (int i = start; i <= end; ++i) {
                maxCore = Math.max(maxCore, core[i]);
                System.out.printf("core[%d]=%d\n", i, core[i]);
                writer.write("core[" + i + "]=" + core[i] + "\n");
            }
            writer.write("maxCore=" + maxCore);
            writer.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }


    public void coreDecomposition() {
        int[] degree = new int[end + 1];
        boolean[] deleteFlag = new boolean[end + 1];
        int[] first = new int[end + 1];

        // 添加边
        addEdge(first, degree);

        List<Node> nodeList = new ArrayList<>();
        // 设置度
        for (int i = start; i <= end; ++i) {
            nodeList.add(new Node(i, degree[i]));
        }

        // 排序
        Collections.sort(nodeList);

        core = new int[end + 1];
        // core分解算法
        while (!nodeList.isEmpty()) {
            // 得到最小度和顶点
            Node node = nodeList.get(0);
            int deg = node.getDegree();
            int v = node.getV();

            // 为该顶点赋值核心数
            core[v] = deg;
            // 删除该顶点
            deleteFlag[v] = true;
            degree[v] = 0;

            // 更新剩余顶点的度
            updateNodeDegree(v, deleteFlag, degree, first);

            // flag标识剩余顶点中是否有度小于等于deg的顶点
            boolean flag = true;
            while (flag) {
                flag = false;
                // 删除剩余顶点中度小于等于deg的顶点
                for (int i = 1; i < nodeList.size(); ++i) {
                    Node tmp = nodeList.get(i);
                    if (!deleteFlag[tmp.getV()] && degree[tmp.getV()] <= deg) {
                        flag = true;
                        deleteFlag[tmp.getV()] = true;
                        core[tmp.getV()] = deg;
                        degree[tmp.getV()] = 0;
                        // 更新剩余顶点的度
                        updateNodeDegree(tmp.getV(), deleteFlag, degree, first);
                    }
                }
            }

            // 按照新的度重新排序
            nodeList = new ArrayList<>();
            for (int i = start; i <= end; ++i) {
                if (!deleteFlag[i]) {
                    nodeList.add(new Node(i, degree[i]));
                }
            }
            Collections.sort(nodeList);
        }
    }

    public void kCoreCommunitySearchNoRead(int k, String outputFileName) {
        coreDecomposition();
        // 将结果写入文件
        //writeFile(core, outputFileName);

        DisJointSet disJointSet = new DisJointSet(end);

        boolean[] flag = new boolean[end + 1];
        for (Edge edge : edgeList) {
            int u = edge.getU();
            int v = edge.getV();
            if (core[u] >= k && core[v] >= k) {
                disJointSet.join(u, v);
                flag[u] = true;
                flag[v] = true;
            }
        }
        int[] pre = new int[end + 1];

        // 更新每个节点的祖先节点
        for (int i = start; i <= end; ++i) {
            pre[i] = disJointSet.find(i);
//            System.out.printf("pre[%d]=%d\n", i, pre[i]);
        }

        int maxCommunitySize = 0;
        int communityCount = 0;
        int nodeCount = 0;
        for (int i = start; i <= end; ++i) {
            if (flag[i] && pre[i] == i) {
                ++communityCount;
                System.out.printf("第" + communityCount + "个社区的成员为：");
                int num = 0;
                for (int j = start; j <= end; ++j) {
                    if (pre[j] == i) {
                        ++num;
                        System.out.printf("%d ", j);
                    }
                }
                nodeCount += num;
                maxCommunitySize = Math.max(maxCommunitySize, num);
                System.out.println();
                System.out.println("第" + communityCount + "个社区总共有" + num + "个成员");
            }
        }

        System.out.println("共找到" + communityCount + "个" + k + "-core社区");
        if (communityCount != 0) {
            int avgCommunitySize = nodeCount / communityCount;
            System.out.println("其中最大的社区的大小为" + maxCommunitySize + "，平均社区大小为" + avgCommunitySize);
            dataStatistics(maxCommunitySize, communityCount, avgCommunitySize, k, outputFileName);
        } else {
            dataStatistics(0, 0, 0, k, outputFileName);
        }
    }


}
